#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using pii = pair < int , int >;
using vec = vector < int >;
using veg = vector < pii >;
using ll = long long;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int pot[N],cnt,f[N],n,K,ans;
int upd(int x) { return x + (x >> 31 & mod); }
ll qp(ll x,int t) { ll res = 1; for(; t; t >>= 1,x = x * x % mod) if(t & 1) res = res * x % mod; return res; }

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n = in,K = in;
	rep(i, 1, n) {
		if(i * i > n) break;
		if(n % i) continue;
		pot[++cnt] = i; if(i * i ^ n) pot[++cnt] = n / i;
	}
	sort(pot + 1,pot + cnt + 1);
	rep(i, 1, cnt) {
		f[i] = qp(K,pot[i] + 1 >> 1);
		rep(j, 1, i - 1) if(pot[i] % pot[j] == 0) f[i] = upd(f[i] - f[j]);
		if(pot[i] & 1) ans = upd(ans + 1ll * f[i] * pot[i] % mod - mod);
		else ans = upd(ans + 1ll * f[i] * (pot[i] >> 1) % mod - mod);
	}
	cout << ans << endl; return 0;
}
